# -*- coding:utf-8 -*-

# author: firstoneyuan
# email: devops_yj@163.com

# 杨辉三角的基本实现(方法1)
# 下一行依赖上一行所有元素,是上一行所有元素的两两相加的和,再在两头各加1.
# 预先构建前两行,从而推导出后面的所有行

triangle = [[1],[1,1]]

for i in range(2,6):
    cur = [1]
    pre = triangle[i-1]
    for j in range(len(pre)-1):
        cur.append(pre[j]+pre[j+1])
    cur.append(1)
    triangle.append(cur)
print(triangle)

# 变体,从第一行开始
triangle = []
n = 6
for i in range(n):
    cur = [1]
    triangle.append(cur)

    if i == 0:
        continue

    pre = triangle[i-1]
    for j in range(len(pre)-1):
        cur.append(pre[j]+pre[j+1])
    cur.append(1)
print(triangle)



'''
补零(方法二)
除了第一行,每一行每一个元素都是由上一行的元素相加得到,如何得到两头的1呢?
目标是打印指定的行,所以算出一行就打印一行,不需要用一个大空间存储所有已经算出的行.
'''
# while循环实现
n = 6
newline = [1] #相当于计算好的第一行
print(newline)

for i in range(1,n):
    oldline = newline.copy() #浅拷贝并补0
    oldline.append(0) #尾部补0相当于两端补0
    newline.clear() #使用append,所以要清除.

    offset = 0
    while offset <= i:
        newline.append(oldline[offset-1] + oldline[offset])
        offset += 1
    print(newline)

# for循环实现
n = 6
newline = [1] #相当于计算好的第一行
print(newline)

for i in range(1,n):
    oldline = newline.copy()  #浅拷贝并补0
    oldline.append(0)  #尾部补0相当于两端补0
    newline.clear() #使用append,所以要清除.

    for j in range(i+1):
        newline.append(oldline[j - 1] + oldline[j])
    print(newline)


'''
对称性(方法3)
思路:
能不能一次性开辟空间,可以使用列表解析式或者循环迭代方式
能不能减少一半的数字计算.
'''

triangle = []
n = 6
for i in range(n):
    row = [1] #开始的1
    for k in range(i):  # 中间填0,尾部填1
        row.append(1) if k == i-1 else row.append(0)
    triangle.append(row)
    if i == 0:
        continue
    for j in range(1,i//2+1): #i = 2 第三行才能进来.
        # print(i,j)
        val = triangle[i - 1][j-1] + triangle[i,-1][j]
        row[j] = val
        # i 为2,j为0 1 2，循环1次
        # i 为3,j为0 1 2 3， 循环1次
        # i为4,j 为0 1 2 3 4，循环2次.
        if i != 2*j: #奇数个数的中点跳过.
            row[-j-1] = val 

print(triangle)

# 简化代码
triangle = []
n = 6
for i in range(n):
    row = [1] * (i+1)  # 一次性开辟
    triangle.append(row)
    for j in range(1,i//2+1): #i=2第三行才能进来.
        # print(i,j)
        val = triangle[i - 1][j-1] + triangle[i - 1][j]
        row[j] = val 
        if i != 2*j: #奇数个数的中点跳过.
            row[-j-1] = val 

print(triangle)


# 单行覆盖(方法4)
# 使用方法3的对称性,只开辟一个列表
n = 6

row = [1] * n  #一次性开辟足够的空间

for i in range(n):
    offset = n - i 
    z = 1 #因为会有覆盖影响计算,所以引入一个临时变量.
    for j in range(1,i//2+1): #对称性
        val = z + row[j]
        row[j],z = val,row[j]
        if i != 2*j:
            row[-j-offset] = val 
    print(row[:i+1])

    